package com.hgc.ch02.sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1、什么是最小生成树
 * 现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
 * 于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，
 * 每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，
 * 每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
 * 
 * @author 01385936
 *
 */
public class Graph {

	/**
	 * 已经选上的点
	 */
	private List<Point> points = new ArrayList<Point>();
	/**
	 * 未选择的点
	 */
	private List<Point> notPs = new ArrayList<Point>();
	/**
	 * 边集合 key - value
	 */
	private Map<String, UnDirectedEdge> edges = new HashMap<String, UnDirectedEdge>();
	/**
	 * 最小边集合
	 */
	private List<UnDirectedEdge> minNns = new ArrayList<UnDirectedEdge>();

	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		Graph g = new Graph();
		int[][] array = g.createGraph();
		List<Point> list = g.findMinWay(array, g.getPoints().get(0));
		for (Point p : list) {
			System.out.print(String.format("%11s", p.getPointName()));
		}
		System.out.println("");
		for (UnDirectedEdge un : g.getMinNns()) {
			System.out.println(String.format("%s--->%s---%s", un.getFrom().getPointName(), un.getTo().getPointName(),
					un.getWeight()));
		}
		System.out.println(System.currentTimeMillis() - time);
	}

	private List<Point> findMinWay(int[][] array, Point startP) {
		List<Point> list = new ArrayList<Point>();
		notPs.addAll(points);
		list.add(startP);
		notPs.remove(startP);
		findMinWayBase(array, list);
		return list;
	}

	private void findMinWayBase(int[][] array, List<Point> ps) {
		if (ps.size() >= points.size() || notPs.isEmpty()) {
			return;
		}
		int min = Integer.MAX_VALUE;
		UnDirectedEdge minUn = null;
		for (Point p : ps) {
			for (Point notp : notPs) {
				UnDirectedEdge un = edges.get(UnDirectedEdge.createKey(p.getPointName(), notp.getPointName()));
				if (un != null && un.getWeight() != Integer.MAX_VALUE) {
					if (min > un.getWeight()) {
						minUn = un;
						min = un.getWeight();
					}
				}
			}
		}
		if (minUn != null) {
			minNns.add(minUn);
			System.out.println(minUn.toString());
		}
		if (minUn != null && !ps.contains(minUn.getTo())) {
			ps.add(minUn.getTo());
			notPs.remove(minUn.getTo());
		}
		if (minUn != null && !ps.contains(minUn.getFrom())) {
			ps.add(minUn.getFrom());
			notPs.remove(minUn.getFrom());
		}
		findMinWayBase(array, ps);
	}

	private boolean exsist(int i, List<Point> ps) {
		for (Point p : ps) {
			boolean flag = p.getPointName().equals(i + "");
			if (flag) {
				return flag;
			}
		}
		return false;
	}

	public int[][] createGraph() {
		Point p1 = new Point("1");
		points.add(p1);
		Point p2 = new Point("2");
		points.add(p2);
		Point p3 = new Point("3");
		points.add(p3);
		Point p4 = new Point("4");
		points.add(p4);
		Point p5 = new Point("5");
		points.add(p5);
		Point p6 = new Point("6");
		points.add(p6);
		Point p7 = new Point("7");
		points.add(p7);
		Point p8 = new Point("8");
		points.add(p8);

		UnDirectedEdge edge1 = new UnDirectedEdge(p1, p2, 1);
		UnDirectedEdge edge2 = new UnDirectedEdge(p1, p3, 8);
		UnDirectedEdge edge3 = new UnDirectedEdge(p1, p4, 3);
		UnDirectedEdge edge4 = new UnDirectedEdge(p3, p7, 9);
		UnDirectedEdge edge5 = new UnDirectedEdge(p3, p4, 4);
		UnDirectedEdge edge6 = new UnDirectedEdge(p2, p4, 6);
		UnDirectedEdge edge7 = new UnDirectedEdge(p2, p8, 7);
		UnDirectedEdge edge8 = new UnDirectedEdge(p4, p8, 4);
		UnDirectedEdge edge9 = new UnDirectedEdge(p4, p5, 5);
		UnDirectedEdge edge10 = new UnDirectedEdge(p4, p6, 7);
		UnDirectedEdge edge11 = new UnDirectedEdge(p4, p7, 7);
		UnDirectedEdge edge12 = new UnDirectedEdge(p8, p5, 2);
		UnDirectedEdge edge13 = new UnDirectedEdge(p5, p6, 3);
		UnDirectedEdge edge14 = new UnDirectedEdge(p6, p7, 4);

		edges.put(edge1.getKey(), edge1);
		edges.put(edge1.getReverseKey(), edge1);
		edges.put(edge2.getKey(), edge2);
		edges.put(edge2.getReverseKey(), edge2);
		edges.put(edge3.getKey(), edge3);
		edges.put(edge3.getReverseKey(), edge3);
		edges.put(edge4.getKey(), edge4);
		edges.put(edge4.getReverseKey(), edge4);
		edges.put(edge5.getKey(), edge5);
		edges.put(edge5.getReverseKey(), edge5);
		edges.put(edge6.getKey(), edge6);
		edges.put(edge6.getReverseKey(), edge6);
		edges.put(edge7.getKey(), edge7);
		edges.put(edge7.getReverseKey(), edge7);
		edges.put(edge8.getKey(), edge8);
		edges.put(edge8.getReverseKey(), edge8);
		edges.put(edge9.getKey(), edge9);
		edges.put(edge9.getReverseKey(), edge9);
		edges.put(edge10.getKey(), edge10);
		edges.put(edge10.getReverseKey(), edge10);
		edges.put(edge11.getKey(), edge11);
		edges.put(edge11.getReverseKey(), edge11);
		edges.put(edge12.getKey(), edge12);
		edges.put(edge12.getReverseKey(), edge12);
		edges.put(edge13.getKey(), edge13);
		edges.put(edge13.getReverseKey(), edge13);
		edges.put(edge14.getKey(), edge14);
		edges.put(edge14.getReverseKey(), edge14);

		int[][] array = new int[8][8];
		UnDirectedEdge un = null;
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length; j++) {
				if (i == j) {
					array[i][j] = 0;
				} else {
					un = edges.get(UnDirectedEdge.createKey(i + 1, j + 1));
					if (un == null) {
						array[i][j] = Integer.MAX_VALUE;
					} else {
						array[i][j] = un.getWeight();
					}
				}
			}
		}

		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length; j++) {
				if (array[i][j] == Integer.MAX_VALUE) {
					System.out.print(String.format("%11s", "∞"));
				} else {
					System.out.print(String.format("%11s", array[i][j]));
				}
			}
			System.out.println("");
		}
		return array;
	}

	public List<Point> getPoints() {
		return points;
	}

	public void setPoints(List<Point> points) {
		this.points = points;
	}

	public List<Point> getNotPs() {
		return notPs;
	}

	public void setNotPs(List<Point> notPs) {
		this.notPs = notPs;
	}

	public Map<String, UnDirectedEdge> getEdges() {
		return edges;
	}

	public void setEdges(Map<String, UnDirectedEdge> edges) {
		this.edges = edges;
	}

	public List<UnDirectedEdge> getMinNns() {
		return minNns;
	}

	public void setMinNns(List<UnDirectedEdge> minNns) {
		this.minNns = minNns;
	}

}

class UnDirectedEdge {
	private Point from;
	private Point to;
	private int weight;

	private static final String APP_STR = "_";

	public UnDirectedEdge() {
	}

	public UnDirectedEdge(Point from, Point to, int weight) {
		this.from = from;
		this.to = to;
		this.weight = weight;
	}

	public Point getFrom() {
		return from;
	}

	public void setFrom(Point from) {
		this.from = from;
	}

	public Point getTo() {
		return to;
	}

	public void setTo(Point to) {
		this.to = to;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	public String getKey() {
		return this.from.getPointName() + APP_STR + this.to.getPointName();
	}

	public String getReverseKey() {
		return this.to.getPointName() + APP_STR + this.from.getPointName();
	}

	public static String createKey(int from, int to) {
		return from + APP_STR + to;
	}

	public static String createKey(String from, String to) {
		return from + APP_STR + to;
	}

	@Override
	public String toString() {
		return "unDirectedEdge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
	}

}

class Point {
	private String pointName;

	public Point() {

	}

	public Point(String pointName) {
		this.pointName = pointName;
	}

	public String getPointName() {
		return pointName;
	}

	public void setPointName(String pointName) {
		this.pointName = pointName;
	}

	@Override
	public String toString() {
		return "Point [pointName=" + pointName + "]";
	}

}
